Search results for "Learned Index"
showing 4 items of 4 documents
Standard Vs Uniform Binary Search and Their Variants in Learned Static Indexing: The Case of the Searching on Sorted Data Benchmarking Software Platf…
2023
Learned Indexes are a novel approach to search in a sorted table. A model is used to predict an interval in which to search into and a Binary Search routine is used to finalize the search. They are quite effective. For the final stage, usually, the lower_bound routine of the Standard C++ library is used, although this is more of a natural choice rather than a requirement. However, recent studies, that do not use Machine Learning predictions, indicate that other implementations of Binary Search or variants, namely k-ary Search, are better suited to take advantage of the features offered by modern computer architectures. With the use of the Searching on Sorted Sets SOSD Learned Indexing bench…
Learned Sorted Table Search and Static Indexes in Small-Space Data Models
2023
Machine-learning techniques, properly combined with data structures, have resulted in Learned Static Indexes, innovative and powerful tools that speed up Binary Searches with the use of additional space with respect to the table being searched into. Such space is devoted to the machine-learning models. Although in their infancy, these are methodologically and practically important, due to the pervasiveness of Sorted Table Search procedures. In modern applications, model space is a key factor, and a major open question concerning this area is to assess to what extent one can enjoy the speeding up of Binary Searches achieved by Learned Indexes while using constant or nearly constant-space mod…
Learned Sorted Table Search and Static Indexes in Small Model Space
2022
Machine Learning Techniques, properly combined with Data Structures, have resulted in Learned Static Indexes, innovative and powerful tools that speed-up Binary Search, with the use of additional space with respect to the table being searched into. Such space is devoted to the ML model. Although in their infancy, they are methodologically and practically important, due to the pervasiveness of Sorted Table Search procedures. In modern applications, model space is a key factor and, infact, a major open question concerning this area is to assess to whatextent one can enjoy the speed-up of Learned Indexes while using constant or nearly constant space models.We address it here by (a) introducing…
A Tour of Learned Static Sorted Sets Dictionaries: From Specific to Generic with an Experimental Performance Analysis
2022
In recent years, in the era of Big Data, studying new methods to improve the performance of well-known procedures, such as searching in a Sorted Set, has become crucial in many fields. A new trend emerging in this scenario combines Machine Learning models with Data Structures, generating the so-called Learned Data Structures. In this thesis, we provide an in-depth experimental study of the use of these models, starting from some evidence known to experts in the field but not experimentally investigated concerning the use of very complex models such as Neural Networks. Then, we document a time/space trade-off scenario that is very important for practitioners and designers users. Furthermore,…